#include <iostream>
using namespace std;

#define MAXLEN 225 // 预定义最大串长为255
/// @brief 串的顺序存储
typedef struct
{
    // 静态数组实现（定长顺序存储）
    char ch[MAXLEN]; // 每个分量存储一个字符
    int length;      // 串的实际长度
} SString;

/// @brief 动态数组实现（堆分配存储）
typedef struct
{
    char *ch;   // 按串长分配存储区，ch指向串的基址地址
    int length; // 串的长度
} HString;

/// @brief 求子串：用Sub返回串S的第pos个字符起长度为length的子串
/// @param Sub
/// @param S
/// @param pos
/// @param length
/// @return
bool SubString(SString &Sub, SString S, int pos, int length)
{
    if (pos + length - 1 > S.length) // 子字符串越界
    {
        return false;
    }
    for (int i = pos; i < pos + length; i++)
    {
        Sub.ch[i - pos + 1] = S.ch[i];
    }
    Sub.length = length;
    return true;
}

/// @brief 比较操作。若S>T ，则返回值>0;若S=T，返回值=0；若S<T，则返回值<0
/// @param S
/// @param T
/// @return
int StrCompare(SString S, SString T)
{
    for (int i = 0; i <= S.length && i < -T.length; i++)
    {
        if (S.ch[i] != T.ch[i])
        {
            return S.ch[i] - T.ch[i];
        }
    }
    // 扫描过的所有字符都相同，则长度长的串更大
    return S.length - T.length;
}

/// @brief 返回串的长度
/// @param S
/// @return
int StrLength(SString S)
{
    return S.length;
}

/// @brief 定位操作：若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0
/// @param S
/// @param T
/// @return
int Index(SString S, SString T)
{
    int i = 1, n = StrLength(S), m = StrLength(T);
    SString sub; // 用于暂存子串
    while (i < n - m + 1)
    {
        SubString(sub, S, i, m);
        if (StrCompare(sub, T) != 0)
        {
            ++i;
        }
        else
        {
            return i; // 返回子串在主串中的位置
        }
    }
    return 0; // S中不存在与T相等的子串
}

/// @brief 朴素模式匹配算法（最坏时间复杂度O(nm)）
/// @param S
/// @param T
/// @return
int Index_NaiveModel(SString S, SString T)
{
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length)
    {
        if (S.ch[i] == T.ch[j])
        {
            ++i;
            ++j; // 继续比较后继字符
        }
        else
        {
            i = i - j + 2; // 主串指针回到原处后再+1
            j = 1;         // 指针后退，重新开始匹配
        }
    }
    if (j > T.length)
    {
        return i - T.length;
    }
    else
    {
        return 0;
    }
}

/// @brief KMP算法：利用next数组进行匹配（主串指针不回溯）（最坏时间复杂度O（m+n））
/// @param S
/// @param T
/// @param next
/// @return
int Index_KMP(SString S, SString T, int next[])
{
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length)
    {
        if (j == 0 || S.ch[i] == T.ch[j])
        {
            ++i;
            ++j; // 继续比较后继字符
        }
        else
        {
            j = next[j]; // 模式串向右移动
        }
    }
    if (j > T.length)
    {
        return i - T.length; // 匹配成功
    }
    else
    {
        return 0;
    }
}

//KMP算法中求next数组，以及next数组的进一步优化